package leetcode;

/*
720. 词典中最长的单词
给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。
若无答案，则返回空字符串。
示例 1：
输入：
words = ["w","wo","wor","worl", "world"]
输出："world"
解释：
单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。
示例 2：
输入：
words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释：
"apply"和"apple"都能由词典中的单词组成。但是"apple"的字典序小于"apply"。
提示：
所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。
*/

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class problems_720 {
    public static void main(String[] args) {
        System.out.println(new Solution().longestWord(new String[]{"rac", "rs", "ra", "on", "r", "otif", "o", "onpdu", "rsf", "rs", "ot", "oti", "racy", "onpd"}));
    }

    static class Solution {
        public String longestWord(String[] words) {
            // 根据长度排序
            Arrays.sort(words, new Comparator<String>() {
                public int compare(String s1, String s2) {
                    return s1.length() - s2.length();
                }
            });
            String res = "";
            Set<String> set = new HashSet();
            // 遍历
            for (String s : words) {
                //
                if (s.length() <= 1 || set.contains(s.substring(0, s.length() - 1))) {
                    set.add(s);
                    if (s.length() > res.length() || (s.length() == res.length() && s.compareTo(res) < 0)) {
                        res = s;
                    }
                }
            }
            return res;
        }
    }


//    static class Solution {
//        List<Integer> userd = new ArrayList<>();
//        List<String> ret = new ArrayList<>();
//        int max = 0;
//        public String longestWord(String[] words) {
//            for (int i = 0; i < words.length; i++) {
//                String word = words[i];
//                if (word.length() == 1) {
//                    dfs(words, word);
//                }
//            }
//            String[] retArr = ret.toArray(new String[ret.size()]);
//            Arrays.sort(retArr);
//            return retArr[0];
//        }
//
//        private void dfs(String[] words, String str) {
//            if(null != str){
//                if(max < str.length()){
//                    max = str.length();
//                    ret = new ArrayList<>();
//                }
//                if(max == str.length()) ret.add(str);
//            }
//
//            // 寻找下一字符
//            String lastWord = str;
//            for (int i = 0; i < words.length; i++) {
//                if (userd.contains(i)) continue;
//                String word = words[i];
//                if (word.length() == lastWord.length() + 1 && word.indexOf(lastWord) == 0) {
//                    userd.add(i);
//                    dfs(words, word);
//                }
//            }
//        }
//    }


//    static class Solution {
//        List<Integer> userd = new ArrayList<>();
//        public String longestWord(String[] words) {
//            int max = 0;
//            List<String> list = null;
//            // 取得单字节的首字母
//            for (int i = 0; i < words.length; i++) {
//                String word = words[i];
//                if (word.length() == 1) {
//                    // 取得首字母后，取得相应字符链
//                    List<String> listWord = new ArrayList<>();
//                    listWord.add(word);
//                    findNext(words, listWord);
//                    // 判断是否是最大
//                    String str = listWord.get(listWord.size() - 1);
//                    if(max < str.length()){
//                        max = str.length();
//                        list = new ArrayList<>();
//                    }
//                    if(max == str.length()) list.add(str);
//                }
//            }
//            String[] ret = list.toArray(new String[list.size()]);
//            Arrays.sort(ret);
//            return ret[0];
//        }
//
//        private void findNext(String[] words, List<String> list) {
//            List<String> listNext = new ArrayList<>();
//            // 寻找下一字符
//            String lastWord = list.get(list.size() - 1);
//            for (int i = 0; i < words.length; i++) {
//                if (userd.contains(i)) continue;
//                String word = words[i];
//                if (word.length() == lastWord.length() + 1 && word.indexOf(lastWord) == 0) {
//                    userd.add(i);
//                    listNext.add(word);
//                }
//            }
//            // 排序后取值
//            if(!listNext.isEmpty()){
//                String[] arrString = listNext.stream().sorted().toArray(String[]::new);
//                list.add(arrString[0]);
//                findNext(words, list);
//            }
//        }
//    }
}